Total Hamming Distance

LeetCode 477 | Difficulty: Medium

Medium

Problem Description

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

Example 1:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

Constraints:

- `1 <= nums.length <= 10^4`

- `0 <= nums[i] <= 10^9`

- The answer for the given input will fit in a **32-bit** integer.

Topics: Array, Math, Bit Manipulation

---

Approach

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

---

Solutions

Solution 1: C# (Best: 288 ms)

Metric	Value
Runtime	288 ms
Memory	N/A
Date	2018-08-19

Solution

public class Solution {
    public int TotalHammingDistance(int[] nums)
{
    int len = nums.Length;
    int[] nonZeroes = new int[32];
    foreach (var num in nums)
    {
        int n = num;
        int index=31;
        while(n!=0)
        {
            if(n%2!=0)  nonZeroes[index]++;
            index--;
            n = n/2;
        }   
    }
    
    int result = 0;
    for (int i = 0; i < 32; i++)
    {
        result += nonZeroes[i] * (len-nonZeroes[i]);
    }
    return result;
}
}

---

Complexity Analysis

Approach	Time	Space
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.